package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-02-29 23:19
 */
public class QLint178 {
    private int[] father;

    private int find(int x) {
        if(x == father[x]) {
            return x;
        }

        return father[x] = find(father[x]);
    }

    public boolean validTree(int n, int[][] edges) {
        if (n == 0) {
            return false;
        }

        if (edges.length != n - 1) {
            return false;
        }

        father = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }

        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];

            int fatherX = find(x);
            int fatherY = find(y);

            if(fatherX == fatherY) {
                return false;
            }

            father[fatherX] = fatherY;
        }

        return true;
    }
}
